'''
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格都的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。

 

示例 1：


输入：grid = [[0,1],[1,0]]
输出：2
示例 2：


输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4
示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
import collections
class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if grid[0][0] == 1:
            return -1
        length = len(grid)
        tuple_offset = ((1, 0), (0, 1), (1, 1), (-1, 0), (0, -1), (1, -1), (-1, 1), (-1, -1))
        deq = collections.deque([[0, 0]])
        dis = 0
        visited = set()
        visited.add((0, 0))
        while deq:
            len_cur = len(deq)
            dis += 1
            for _ in range(len_cur):
                x, y = deq.popleft()
                if x == length - 1 and y == length - 1:
                    return dis
                for x_offset, y_offset in tuple_offset:
                    new_x, new_y = x + x_offset, y + y_offset
                    if 0 <= new_x < length and 0 <= new_y < length and (new_x, new_y) not in visited and \
                            grid[new_x][new_y] == 0:
                        deq.append([new_x, new_y])
                        visited.add((new_x, new_y))
        return -1


grid = [[0,1,1,0,0,0],
        [0,1,0,1,1,0],
        [0,1,1,0,1,0],
        [0,0,0,1,1,0],
        [1,1,1,1,1,0],
        [1,1,1,1,1,0]]
Solution().shortestPathBinaryMatrix(grid)